package leetcode100;

// TODO 脑筋急转弯 【-】 下一个排列
// TODO https://leetcode.cn/problems/next-permutation/solution/jie-fa-hen-jian-dan-jie-shi-qi-lai-zen-yao-jiu-na-/

public class lc100_0031 {

    public void nextPermutation(int[] nums) {
        int n = nums.length;

        // 寻找第一个小于右邻居的数
        int curr = n - 1;
        for (; curr > 0 && nums[curr] <= nums[curr-1]; curr--) {
        }
        if (curr == 0) {    // 没有小于右邻居的数, 直接全部反转
            reverse(nums, 0, n-1);
        } else {
            // 寻找第一个大于 nums[curr-1] 的数
            int i = n-1;
            for (;i >= 0 && nums[i] <= nums[curr-1]; i--) {
            }
            swap(nums, i, curr-1);
            reverse(nums, curr, n-1);
        }

    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void reverse(int[] nums, int start, int end) {
        int left = start, right = end;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

}